﻿//14.Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).


using System;
using System.Collections.Generic;

class QuickSort
{
    static void Main()
    {
        int numberN = int.Parse(Console.ReadLine());
        List<int> quickList = new List<int>();
        for (int i = 0; i < numberN; i++)
        {
            quickList.Add(int.Parse(Console.ReadLine()));
        }

        SortAlgorithm(quickList, 0, quickList.Count - 1);

        foreach (var item in quickList)
        {
            Console.WriteLine(item);
        }
    }

    static void SortAlgorithm(List<int> quickList, int left, int right)
    {
        if (left < right)
        {
            int pivotIndex = (left + right) / 2;
            int pivotNewIndex = Partition(quickList, left, right, pivotIndex);
            SortAlgorithm(quickList, left, pivotNewIndex - 1);
            SortAlgorithm(quickList, pivotNewIndex + 1, right);
        }
    }

    static int Partition(List<int> quickList, int left, int right, int pivotPoint)
    {
        int pivotValue = quickList[pivotPoint];
        quickList[pivotPoint] = quickList[right];
        quickList[right] = pivotValue;
        int storeIndex = left;
        for (int i = left; i < right; i++)
        {
            if (quickList[i] <= pivotValue)             //Понеже алгоритъма е инплементиран за числа, ако искаме да работи за стрингове
                                                        //освен въвеждане на изходните данни като такива разликата е в тази проверка,
                                                        //която трябва да се направи за условието по което искаме да сортираме стриговете.
                                                        //String.Compare(quickList[i], pivotValue) <= 0
            {
                int valueOfI = quickList[i];
                quickList[i] = quickList[storeIndex];
                quickList[storeIndex] = valueOfI;
                storeIndex += 1;
            }
        }
        int valueOfStoreIndex = quickList[storeIndex];
        quickList[storeIndex] = quickList[right];
        quickList[right] = valueOfStoreIndex;
        return storeIndex;
    }

    //static void Print(List<int> quickList)
    //{
    //    foreach (var item in quickList)
    //    {
    //        Console.WriteLine(item);
    //    }
    //}
}
